<!DOCTYPE HTML>
<html>
<head>
<meta charset="UTF-8">
<title>Exercise 4.5: Show the equivalence of 3 convex problem formations</title>
<link rel="canonical" href="/Users/mcgrant/Repos/CVX/examples/cvxbook/Ch04_cvx_opt_probs/html/ex_4_5.html">
<link rel="stylesheet" href="../../../examples.css" type="text/css">
</head>
<body>
<div id="header">
<h1>Exercise 4.5: Show the equivalence of 3 convex problem formations</h1>
Jump to:&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#source">Source code</a>&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#output">Text output</a>
&nbsp;&nbsp;&nbsp;&nbsp;
Plots
&nbsp;&nbsp;&nbsp;&nbsp;<a href="../../../index.html">Library index</a>
</div>
<div id="content">
<a id="source"></a>
<pre class="codeinput">
<span class="comment">% From Boyd &amp; Vandenberghe, "Convex Optimization"</span>
<span class="comment">% Jo&euml;lle Skaf - 08/17/05</span>
<span class="comment">%</span>
<span class="comment">% Shows the equivalence of the following 3 problems:</span>
<span class="comment">% 1) Robust least-squares problem</span>
<span class="comment">%           minimize    sum_{i=1}^{m} phi(a_i'*x - bi)</span>
<span class="comment">%    where phi(u) = u^2             for |u| &lt;= M</span>
<span class="comment">%                   M(2|u| - M)     for |u| &gt;  M</span>
<span class="comment">% 2) Least-squares with variable weights</span>
<span class="comment">%           minimize    sum_{i=1}^{m} (a_i'*x - bi)^2/(w_i+1) + M^2*1'*w</span>
<span class="comment">%               s.t.    w &gt;= 0</span>
<span class="comment">% 3) Quadratic program</span>
<span class="comment">%           minimize    sum_{i=1}^{m} (u_i^2 + 2*M*v_i)</span>
<span class="comment">%               s.t.    -u - v &lt;= Ax - b &lt;= u + v</span>
<span class="comment">%                       0 &lt;= u &lt;= M*1</span>
<span class="comment">%                       v &gt;= 0</span>

<span class="comment">% Generate input data</span>
randn(<span class="string">'state'</span>,0);
m = 16; n = 8;
A = randn(m,n);
b = randn(m,1);
M = 2;

<span class="comment">% (a) robust least-squares problem</span>
disp(<span class="string">'Computing the solution of the robust least-squares problem...'</span>);
cvx_begin
    variable <span class="string">x1(n)</span>
    minimize( sum(huber(A*x1-b,M)) )
cvx_end

<span class="comment">% (b)least-squares problem with variable weights</span>
disp(<span class="string">'Computing the solution of the least-squares problem with variable weights...'</span>);
cvx_begin
    variable <span class="string">x2(n)</span>
    variable <span class="string">w(m)</span>
    minimize( sum(quad_over_lin(diag(A*x2-b),w'+1)) + M^2*ones(1,m)*w)
    w &gt;= 0;
cvx_end

<span class="comment">% (c) quadratic program</span>
disp(<span class="string">'Computing the solution of the quadratic program...'</span>);
cvx_begin
    variable <span class="string">x3(n)</span>
    variable <span class="string">u(m)</span>
    variable <span class="string">v(m)</span>
    minimize( sum(square(u) +  2*M*v) )
    A*x3 - b &lt;= u + v;
    A*x3 - b &gt;= -u - v;
    u &gt;= 0;
    u &lt;= M;
    v &gt;= 0;
cvx_end

<span class="comment">% Display results</span>
disp(<span class="string">'------------------------------------------------------------------------'</span>);
disp(<span class="string">'The optimal solutions for problem formulations 1, 2 and 3 are given'</span>);
disp(<span class="string">'respectively as follows (per column): '</span>);
[x1 x2 x3]
</pre>
<a id="output"></a>
<pre class="codeoutput">
Computing the solution of the robust least-squares problem...
 
Calling Mosek 9.1.9: 152 variables, 64 equality constraints
------------------------------------------------------------

MOSEK Version 9.1.9 (Build date: 2019-11-21 11:32:15)
Copyright (c) MOSEK ApS, Denmark. WWW: mosek.com
Platform: MACOSX/64-X86

Problem
  Name                   :                 
  Objective sense        : min             
  Type                   : CONIC (conic optimization problem)
  Constraints            : 64              
  Cones                  : 32              
  Scalar variables       : 152             
  Matrix variables       : 0               
  Integer variables      : 0               

Optimizer started.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator started.
Freed constraints in eliminator : 0
Eliminator terminated.
Eliminator - tries                  : 1                 time                   : 0.00            
Lin. dep.  - tries                  : 1                 time                   : 0.00            
Lin. dep.  - number                 : 0               
Presolve terminated. Time: 0.00    
Problem
  Name                   :                 
  Objective sense        : min             
  Type                   : CONIC (conic optimization problem)
  Constraints            : 64              
  Cones                  : 32              
  Scalar variables       : 152             
  Matrix variables       : 0               
  Integer variables      : 0               

Optimizer  - threads                : 8               
Optimizer  - solved problem         : the dual        
Optimizer  - Constraints            : 24
Optimizer  - Cones                  : 32
Optimizer  - Scalar variables       : 96                conic                  : 80              
Optimizer  - Semi-definite variables: 0                 scalarized             : 0               
Factor     - setup time             : 0.00              dense det. time        : 0.00            
Factor     - ML order time          : 0.00              GP order time          : 0.00            
Factor     - nonzeros before factor : 180               after factor           : 180             
Factor     - dense dim.             : 0                 flops                  : 5.64e+03        
ITE PFEAS    DFEAS    GFEAS    PRSTATUS   POBJ              DOBJ              MU       TIME  
0   2.0e+00  2.0e+00  2.5e+01  0.00e+00   1.600000000e+01   -8.000000000e+00  1.0e+00  0.00  
1   4.1e-01  4.1e-01  3.9e+00  5.26e-02   1.772761786e+00   -5.760426069e+00  2.1e-01  0.01  
2   8.9e-02  8.9e-02  4.1e-01  7.48e-01   4.160217895e+00   2.359199320e+00   4.5e-02  0.01  
3   2.3e-02  2.3e-02  5.2e-02  9.67e-01   4.210999257e+00   3.748912815e+00   1.1e-02  0.01  
4   7.6e-03  7.6e-03  1.0e-02  1.00e+00   4.222835207e+00   4.069222755e+00   3.8e-03  0.01  
5   2.4e-03  2.4e-03  1.8e-03  1.00e+00   4.209102647e+00   4.160168718e+00   1.2e-03  0.01  
6   3.4e-04  3.4e-04  9.6e-05  1.00e+00   4.209726646e+00   4.202854232e+00   1.7e-04  0.01  
7   5.0e-06  5.0e-06  1.7e-07  1.00e+00   4.209707372e+00   4.209605489e+00   2.5e-06  0.01  
8   5.1e-08  5.1e-08  1.7e-10  1.00e+00   4.209705258e+00   4.209704232e+00   2.5e-08  0.01  
9   2.6e-09  2.7e-09  2.1e-12  1.00e+00   4.209705215e+00   4.209705162e+00   1.3e-09  0.01  
Optimizer terminated. Time: 0.02    


Interior-point solution summary
  Problem status  : PRIMAL_AND_DUAL_FEASIBLE
  Solution status : OPTIMAL
  Primal.  obj: 4.2097052151e+00    nrm: 2e+00    Viol.  con: 2e-16    var: 1e-09    cones: 3e-09  
  Dual.    obj: 4.2097051615e+00    nrm: 4e+00    Viol.  con: 0e+00    var: 4e-09    cones: 0e+00  
Optimizer summary
  Optimizer                 -                        time: 0.02    
    Interior-point          - iterations : 9         time: 0.01    
      Basis identification  -                        time: 0.00    
        Primal              - iterations : 0         time: 0.00    
        Dual                - iterations : 0         time: 0.00    
        Clean primal        - iterations : 0         time: 0.00    
        Clean dual          - iterations : 0         time: 0.00    
    Simplex                 -                        time: 0.00    
      Primal simplex        - iterations : 0         time: 0.00    
      Dual simplex          - iterations : 0         time: 0.00    
    Mixed integer           - relaxations: 0         time: 0.00    

------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +4.20971
 
Computing the solution of the least-squares problem with variable weights...
 
Calling Mosek 9.1.9: 304 variables, 40 equality constraints
   For improved efficiency, Mosek is solving the dual problem.
------------------------------------------------------------

MOSEK Version 9.1.9 (Build date: 2019-11-21 11:32:15)
Copyright (c) MOSEK ApS, Denmark. WWW: mosek.com
Platform: MACOSX/64-X86

Problem
  Name                   :                 
  Objective sense        : min             
  Type                   : CONIC (conic optimization problem)
  Constraints            : 40              
  Cones                  : 16              
  Scalar variables       : 304             
  Matrix variables       : 0               
  Integer variables      : 0               

Optimizer started.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator started.
Freed constraints in eliminator : 16
Eliminator terminated.
Eliminator started.
Freed constraints in eliminator : 0
Eliminator terminated.
Eliminator - tries                  : 2                 time                   : 0.00            
Lin. dep.  - tries                  : 1                 time                   : 0.00            
Lin. dep.  - number                 : 0               
Presolve terminated. Time: 0.00    
Problem
  Name                   :                 
  Objective sense        : min             
  Type                   : CONIC (conic optimization problem)
  Constraints            : 40              
  Cones                  : 16              
  Scalar variables       : 304             
  Matrix variables       : 0               
  Integer variables      : 0               

Optimizer  - threads                : 8               
Optimizer  - solved problem         : the primal      
Optimizer  - Constraints            : 24
Optimizer  - Cones                  : 16
Optimizer  - Scalar variables       : 48                conic                  : 48              
Optimizer  - Semi-definite variables: 0                 scalarized             : 0               
Factor     - setup time             : 0.00              dense det. time        : 0.00            
Factor     - ML order time          : 0.00              GP order time          : 0.00            
Factor     - nonzeros before factor : 180               after factor           : 180             
Factor     - dense dim.             : 0                 flops                  : 5.60e+03        
ITE PFEAS    DFEAS    GFEAS    PRSTATUS   POBJ              DOBJ              MU       TIME  
0   2.0e+00  1.5e+00  1.0e+00  0.00e+00   0.000000000e+00   0.000000000e+00   1.0e+00  0.00  
1   2.9e-01  2.2e-01  1.5e-01  -2.40e-01  -7.426102505e+00  -6.708055895e+00  1.4e-01  0.01  
2   2.2e-02  1.6e-02  4.3e-03  5.64e-01   -1.916059676e+01  -1.903705542e+01  1.1e-02  0.01  
3   2.1e-04  1.6e-04  4.1e-06  9.60e-01   -2.019946035e+01  -2.019820045e+01  1.1e-04  0.01  
4   5.4e-06  4.1e-06  1.7e-08  1.00e+00   -2.020942828e+01  -2.020939573e+01  2.7e-06  0.01  
5   4.5e-07  3.3e-07  4.0e-10  1.00e+00   -2.020968252e+01  -2.020967986e+01  2.2e-07  0.01  
6   4.8e-08  3.6e-08  1.4e-11  1.00e+00   -2.020970278e+01  -2.020970249e+01  2.4e-08  0.01  
7   1.3e-08  4.9e-09  7.2e-13  1.00e+00   -2.020970488e+01  -2.020970484e+01  3.3e-09  0.01  
Optimizer terminated. Time: 0.02    


Interior-point solution summary
  Problem status  : PRIMAL_AND_DUAL_FEASIBLE
  Solution status : OPTIMAL
  Primal.  obj: -2.0209704882e+01   nrm: 4e+00    Viol.  con: 4e-08    var: 0e+00    cones: 0e+00  
  Dual.    obj: -2.0209704843e+01   nrm: 1e+00    Viol.  con: 0e+00    var: 1e-08    cones: 0e+00  
Optimizer summary
  Optimizer                 -                        time: 0.02    
    Interior-point          - iterations : 7         time: 0.01    
      Basis identification  -                        time: 0.00    
        Primal              - iterations : 0         time: 0.00    
        Dual                - iterations : 0         time: 0.00    
        Clean primal        - iterations : 0         time: 0.00    
        Clean dual          - iterations : 0         time: 0.00    
    Simplex                 -                        time: 0.00    
      Primal simplex        - iterations : 0         time: 0.00    
      Dual simplex          - iterations : 0         time: 0.00    
    Mixed integer           - relaxations: 0         time: 0.00    

------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +4.2097
 
Computing the solution of the quadratic program...
 
Calling Mosek 9.1.9: 128 variables, 56 equality constraints
   For improved efficiency, Mosek is solving the dual problem.
------------------------------------------------------------

MOSEK Version 9.1.9 (Build date: 2019-11-21 11:32:15)
Copyright (c) MOSEK ApS, Denmark. WWW: mosek.com
Platform: MACOSX/64-X86

Problem
  Name                   :                 
  Objective sense        : min             
  Type                   : CONIC (conic optimization problem)
  Constraints            : 56              
  Cones                  : 16              
  Scalar variables       : 128             
  Matrix variables       : 0               
  Integer variables      : 0               

Optimizer started.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator started.
Freed constraints in eliminator : 0
Eliminator terminated.
Eliminator - tries                  : 1                 time                   : 0.00            
Lin. dep.  - tries                  : 1                 time                   : 0.00            
Lin. dep.  - number                 : 0               
Presolve terminated. Time: 0.00    
Problem
  Name                   :                 
  Objective sense        : min             
  Type                   : CONIC (conic optimization problem)
  Constraints            : 56              
  Cones                  : 16              
  Scalar variables       : 128             
  Matrix variables       : 0               
  Integer variables      : 0               

Optimizer  - threads                : 8               
Optimizer  - solved problem         : the primal      
Optimizer  - Constraints            : 40
Optimizer  - Cones                  : 16
Optimizer  - Scalar variables       : 128               conic                  : 48              
Optimizer  - Semi-definite variables: 0                 scalarized             : 0               
Factor     - setup time             : 0.00              dense det. time        : 0.00            
Factor     - ML order time          : 0.00              GP order time          : 0.00            
Factor     - nonzeros before factor : 340               after factor           : 340             
Factor     - dense dim.             : 0                 flops                  : 6.76e+03        
ITE PFEAS    DFEAS    GFEAS    PRSTATUS   POBJ              DOBJ              MU       TIME  
0   4.0e+00  8.0e+00  2.5e+01  0.00e+00   1.600000000e+01   -8.000000000e+00  1.0e+00  0.00  
1   6.8e-01  1.4e+00  4.6e+00  -3.93e-01  -1.940066974e+01  -2.754748703e+01  1.7e-01  0.01  
2   1.3e-01  2.7e-01  4.2e-01  6.76e-01   -5.357917364e+00  -7.159690897e+00  3.3e-02  0.01  
3   4.3e-02  8.6e-02  7.5e-02  9.85e-01   -4.471826379e+00  -5.054170932e+00  1.1e-02  0.01  
4   1.7e-02  3.4e-02  1.8e-02  1.00e+00   -4.360094607e+00  -4.589807682e+00  4.2e-03  0.01  
5   6.6e-03  1.3e-02  4.3e-03  1.01e+00   -4.240156456e+00  -4.330398655e+00  1.7e-03  0.01  
6   1.8e-03  3.5e-03  5.8e-04  1.00e+00   -4.220572075e+00  -4.244669924e+00  4.4e-04  0.01  
7   2.1e-04  4.3e-04  2.4e-05  1.00e+00   -4.210448264e+00  -4.213375005e+00  5.3e-05  0.01  
8   2.8e-06  5.5e-06  3.6e-08  1.00e+00   -4.209715109e+00  -4.209753126e+00  6.9e-07  0.01  
9   6.2e-08  1.2e-07  1.2e-10  1.00e+00   -4.209705505e+00  -4.209706361e+00  1.6e-08  0.01  
10  6.1e-09  1.2e-08  3.7e-12  1.00e+00   -4.209705243e+00  -4.209705326e+00  1.5e-09  0.01  
11  6.7e-10  1.3e-09  1.3e-13  1.00e+00   -4.209705215e+00  -4.209705225e+00  1.7e-10  0.01  
Optimizer terminated. Time: 0.02    


Interior-point solution summary
  Problem status  : PRIMAL_AND_DUAL_FEASIBLE
  Solution status : OPTIMAL
  Primal.  obj: -4.2097052154e+00   nrm: 4e+00    Viol.  con: 2e-09    var: 1e-09    cones: 0e+00  
  Dual.    obj: -4.2097052245e+00   nrm: 2e+00    Viol.  con: 0e+00    var: 8e-10    cones: 0e+00  
Optimizer summary
  Optimizer                 -                        time: 0.02    
    Interior-point          - iterations : 11        time: 0.01    
      Basis identification  -                        time: 0.00    
        Primal              - iterations : 0         time: 0.00    
        Dual                - iterations : 0         time: 0.00    
        Clean primal        - iterations : 0         time: 0.00    
        Clean dual          - iterations : 0         time: 0.00    
    Simplex                 -                        time: 0.00    
      Primal simplex        - iterations : 0         time: 0.00    
      Dual simplex          - iterations : 0         time: 0.00    
    Mixed integer           - relaxations: 0         time: 0.00    

------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +4.20971
 
------------------------------------------------------------------------
The optimal solutions for problem formulations 1, 2 and 3 are given
respectively as follows (per column): 

ans =

    0.3888    0.3888    0.3888
    0.1262    0.1262    0.1262
   -0.3337   -0.3337   -0.3337
    0.1326    0.1326    0.1326
    0.5500    0.5500    0.5500
    0.3526    0.3526    0.3526
   -0.6562   -0.6562   -0.6562
    0.8309    0.8309    0.8309

</pre>
</div>
</body>
</html>